package com.example.leetcode.trainingcamp.week1.practice2;

import com.example.leetcode.prcatice.Test;

/**
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test240 {

    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[]nums:matrix) {
            boolean b = erfen(nums,target);
            if (b){
                return b;
            }
        }
        return false;
    }


    public boolean erfen(int[] nums,int target){
        int low = 0,high = nums.length-1;
        if (nums[low] == target || nums[high] == target){
            return true;
        }
        boolean b =false;
        while (low<=high){
            int middle = low + high /2;
            if (nums[middle] < target){
                low = middle+1;
            }else if (nums[middle]>target){
                high = middle -1;
            }else {
                b = true;
                break;
            }
        }
        return b;
    }
}



class Demo240{
    public static void main(String[] args) {
        int[] nums = {2,5,8,12,19};
        int target = 5;
        Test240 t = new Test240();
        boolean b = t.erfen(nums,target);
        System.out.println(b);
    }
}